import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/5/23 21:31
 */
//给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
//示例 1：
//输入：root = [3,9,20,null,null,15,7]
//输出：[[3],[20,9],[15,7]]

// 和二叉树层序遍历思路一致，需要添加flag控制方向
public class Solution103{
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Boolean flag = true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < queue.size(); i++) {
                TreeNode cur = queue.poll();
                if (flag) {
                    level.addLast(cur.val);
                } else {
                    level.addFirst(cur.val);
                }
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            flag = ! flag;
            result.add(level);
        }
        return result;
    }
}
